/*****
 * BAD Nachos Project 2
 * Bryce Groff
 * Aric West
 * David Mau
 */

package nachos.threads;

import nachos.machine.*;

/************ START BADNACHOS CODE ************/
import java.util.LinkedList;
/************ END BADNACHOS CODE ************/


/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the
 * thread that has been waiting longest.
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has
 * the potential to
 * starve a thread if there's always a thread waiting with higher priority.
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class PriorityScheduler extends Scheduler {
  /**
   * Allocate a new priority scheduler.
   */
  public PriorityScheduler() {
  }

  /**
   * Allocate a new priority thread queue.
   *
   * @param	transferPriority	<tt>true</tt> if this queue should
   *					transfer priority from waiting threads
   *					to the owning thread.
   * @return	a new priority thread queue.
   */
  public ThreadQueue newThreadQueue(boolean transferPriority) {
    return new PriorityQueue(transferPriority);
  }

  /**
   * getPriority()
   */
  public int getPriority(KThread thread) {
    Lib.assertTrue(Machine.interrupt().disabled());

    return getThreadState(thread).getPriority();
  }

  /**
   * getEffectivePriority()
   */
  public int getEffectivePriority(KThread thread) {
    Lib.assertTrue(Machine.interrupt().disabled());

    return getThreadState(thread).getEffectivePriority();
  }


  /***** NEW CODE ******/
  /**
   * Add a donor thread to the indicated thread.
   *
   * @param thread A resource holding thread recieving a donation to increase its priority.
   * @param donor The thread donating its priority to a thread that is holding a resource that the
   *              donor also wants to acquire.
   */
  public void addDonor(KThread thread, KThread donor) {
    Lib.assertTrue(Machine.interrupt().disabled());
    getThreadState(thread).addDonor(donor);
  }

  /**
   * Remove the thread currently donating its priority to the indicated thread. This will be one
   * of the donating threads with the highest priority.
   *
   * @param thread A resource holding thread recieving a donation to increase its priority.
   */
  public void removeDonor(KThread thread) {
    Lib.assertTrue(Machine.interrupt().disabled());
    getThreadState(thread).removeDonor();
  }
  /***** END NEW CODE ******/


  /**
   * setPriority()
   */
  public void setPriority(KThread thread, int priority) {
    Lib.assertTrue(Machine.interrupt().disabled());

    Lib.assertTrue(priority >= priorityMinimum && priority <= priorityMaximum);

    getThreadState(thread).setPriority(priority);
  }

  /**
   * The self test
   */
  public static void selfTest() {
    PrioritySchedulerTest.runTest();
  }

  /**
   * The default priority for a new thread. Do not change this value.
   */
  public static final int priorityDefault = 1;
  /**
   * The minimum priority that a thread can have. Do not change this value.
   */
  public static final int priorityMinimum = 0;
  /**
   * The maximum priority that a thread can have. Do not change this value.
   */
  public static final int priorityMaximum = 7;

  /**
   * Return the scheduling state of the specified thread.
   *
   * @param	thread The thread whose scheduling state to return.
   * @return The scheduling state of the specified thread.
   */
  protected ThreadState getThreadState(KThread thread) {
    if (thread.schedulingState == null) {
      thread.schedulingState = new ThreadState(thread);
    }
    return (ThreadState) thread.schedulingState;
  }
  //End of PriorityScheduler class's own functions and local variables.




  /**
   * A <tt>ThreadQueue</tt> that sorts threads by priority. Only
   * parts of this are implemented and you should complete it, by adding
   * code wherever you see fit and whichever method you see fit.
   */
  protected class PriorityQueue extends ThreadQueue {
    /***** NEW CODE *****/

    /** List of KThreads ordered in order of arrival. */
    protected LinkedList<KThread> waitingThreads = new LinkedList<KThread>();

    /** Provides a link back to the thread currently using the resource
     * associated with this queue. */
    protected KThread owner;

    /********** END NEW CODE ********/


    PriorityQueue(boolean transferPriority) {
      this.transferPriority = transferPriority;
    }

    /**
     * The thread declares its intent to wait for access to the
     * "resource" guarded by this priority queue. This method is only called
     * if the thread cannot immediately obtain access.
     *
     * @param thread The thread
     *
     * @see nachos.threads.ThreadQueue#waitForAccess
     */
    public void waitForAccess(KThread thread) {
      Lib.assertTrue(Machine.interrupt().disabled());

      /***** NEW CODE *****/
      /* Description:
       * If the waiting thread has a higher effective priority than the current owner and
       * priority donation for this queue is allowed, add the waiting thread as a donor to
       * the holding thread. In either case, add the waiting thread to the end of the
       * waiting list. */

      Lib.assertTrue(this.owner != null);
      if (this.transferPriority && (getEffectivePriority(thread) < getPriority(this.owner))) {
        addDonor(this.owner, thread);
      }
      this.waitingThreads.addLast(thread);
      /***** END NEW CODE *****/
    }


    /**
     * print(): Prints the priority queue, for potential debugging
     */
    public void print() {
      /***** NEW CODE *****/
      /* Print the transfer priority status of the queue, the owner of the resource, the threads
       * waiting, and their effective priorities. */

      System.out.println("transferPriority: " + Boolean.toString(this.transferPriority));
      System.out.println("owner: " + this.owner + " " + getEffectivePriority(this.owner));
      for (KThread t : waitingThreads) {
        System.out.print(t.toString() + " " + getEffectivePriority(t) + " ");
      }
      System.out.println();
      /***** END NEW CODE *****/
    }

    /**
     * The specified thread has received exclusive access, without using
     * <tt>waitForAccess()</tt> or <tt>nextThread()</tt>. Assert that no
     * threads are waiting for access.
     */
    public void acquire(KThread thread) {
      Lib.assertTrue(Machine.interrupt().disabled());

      /***** NEW CODE *****/
      /* Not much actually goes on for an acquire, just updates the owner. */

      Lib.assertTrue(this.waitingThreads.size() == 0);
      this.owner = thread;
      /***** END NEW CODE *****/
    }


    /**
     * Select the next thread in the ThreadQueue
     */
    public KThread nextThread() {
      Lib.assertTrue(Machine.interrupt().disabled());

      /***** NEW CODE *****/
      /* If this method has been called then the owner must have finished and can release the
       * donor that was allowing it to run, if it had one. */
      if (this.transferPriority && (this.owner != null)) {
        removeDonor(this.owner);
      }

      /* Pick a new owner and remove it from the waiting list. */
      this.owner = pickNextThread();
      if (this.owner != null) {
        //Found a waiting thread.
        this.waitingThreads.remove(this.owner);
      }
      return this.owner;
      /***** END NEW CODE *****/
    }

    /**
     * Return the next thread that <tt>nextThread()</tt> would return,
     * without modifying the state of this queue.
     *
     * @return	the next thread that <tt>nextThread()</tt> would
     *		return.
     */
    protected KThread pickNextThread() {
      /***** NEW CODE *****/
      /* Description:
       * Returns null if no threads are waiting. Otherwise iterates through the list of waiting
       * threads and returns the first thread which has no threads with a higher effective priority
       * than it waiting. */
      if (this.waitingThreads.size() == 0) {
        return null;
      }
      KThread nextThread = this.waitingThreads.getFirst();
      for (int i = 1; i < this.waitingThreads.size(); i++) {
        if (getEffectivePriority(this.waitingThreads.get(i))
            < getEffectivePriority(nextThread)) {
          nextThread = this.waitingThreads.get(i);
        }
      }
      return nextThread;
      /***** END NEW CODE *****/
    }

    /**
     * <tt>true</tt> if this queue should transfer priority from waiting
     * threads to the owning thread.
     */
    public boolean transferPriority;

  } // End of PriorityQueue class.



  /**
   * The scheduling state of a thread. This should include the thread's
   * priority, its effective priority, any objects it owns, and the queues
   * it's waiting for, etc. This is a convenience class so that
   * no modification to the KThread class are needed for a new scheduler.
   * Each scheduler keeps track of scheduler specific KThread information
   * in its own declaration of the ThreadState class.
   *
   * @see	nachos.threads.KThread#schedulingState
   */
  protected class ThreadState {

    /**
     * Allocate a new <tt>ThreadState</tt> object and associate it with the
     * specified thread.
     *
     * @param	thread	the thread this state belongs to.
     */
    public ThreadState(KThread thread) {
      this.thread = thread;
      this.priority = priorityDefault;

      /***** NEW CODE *****/
      /* Initialize empty list of donor threads. */
      this.donors = new LinkedList<KThread>();
      /***** END NEW CODE *****/
    }

    /**
     * Return the priority of the associated thread.
     *
     * @return	the priority of the associated thread.
     */
    public int getPriority() {
      return this.priority;
    }

    /**
     * Set the priority of the associated thread to the specified value.
     *
     * @param	priority	the new priority.
     */
    public void setPriority(int priority) {
      this.priority = priority;
    }

    /**
     * Return the effective priority of the associated thread.
     *
     * @return	the effective priority of the associated thread.
     */
    public int getEffectivePriority() {

      /***** NEW CODE *****/
      /* Description:
       * If there are no donors then return the natural priority of the thread. Otherwise get the
       * (recursive) effective priority of the first donor in the donor list (they are ordered in
       * decreasing priority). */
      if (this.donors.size() == 0) {
        return this.priority;
      }
      return getThreadState(this.donors.getFirst()).getEffectivePriority();

      /***** END NEW CODE *****/
    }


    /***** NEW CODE *****/
    /**
     * Add a priority donor to this thread.
     *
     * @param donor KThread that is donating its priority.
     */
    public void addDonor(KThread donor) {
      /* Description:
       * Find the location of the first donor thread with a lower priority than the new donor and
       * insert the new donor before it. */

      if (!this.donors.contains(donor)) {
        //No need to keep reassigning to same thing.
        int i = 0;
        for (; i < this.donors.size(); i++) {
          if (getThreadState(this.donors.get(i)).getEffectivePriority()
              >= getThreadState(donor).getEffectivePriority()) {
            break;
          }
        }
        this.donors.add(i, donor);
      }
    }

    /**
     * Remove the current highest donor to this thread.
     *
     * @param donor KThread that is donating its priority.
     */
    public void removeDonor() {
      if (this.donors.size() > 0) {
        this.donors.removeFirst();
      }
    }
    /***** END NEW CODE *****/

    /** The thread with which this object is associated. */
    protected KThread thread;
    /** The priority of the associated thread. */
    protected int priority;


    /***** NEW CODE *****/

    /** List of threads waiting for this thread to release resources and have donator their own
     * higher priority to this thread. */
    protected LinkedList<KThread> donors;

    /***** END NEW CODE *****/

  } //End of ThreadState class.
} //End of Priority Scheduler class.
